from functools import cache

MOD = 10 ** 9 + 7


# n节点数，不超过m高度
# dp记忆化搜索
@cache
def f(n, m):
    if n == 0: return 1
    if m == 0: return 0
    # root size fixed 1
    res = 0
    # l_size: [0, n-1], r_size:[n-1, 0]
    for l_size in range(n):
        r_size = n - l_size - 1
        res += (f(l_size, m - 1) * f(r_size, m - 1) % MOD)
    return res % MOD

# dp 打表
def g(n, m):
    if n == 0: return 1
    if m == 0: return 0
    # dp的行：高度，列：节点数量
    # dp依赖(上边行的左边列),从上到下填就行
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 1
    for i in range(1, m + 1):
        dp[i][0] = 1
        for j in range(1, n + 1):
            res = 0
            for l_size in range(j):
                r_size = j - l_size - 1
                res += (dp[i - 1][l_size] * dp[i - 1][r_size] % MOD)
            dp[i][j] += res % MOD
    return dp[m][n]

# dp 打表and状态压缩
def g2(n, m):
    if n == 0: return 1
    if m == 0: return 0
    # dp的行：高度，列：节点数量
    # dp依赖(上边行的左边列),从上到下填就行
    # dp = [[0] * (n + 1) for _ in range(m + 1)]
    A = [0] * (n + 1)
    A[0] = 1
    for i in range(1, m + 1):
        B = [0] * (n + 1)
        B[0] = 1
        for j in range(1, n + 1):
            res = 0
            for l_size in range(j):
                r_size = j - l_size - 1
                res += (A[l_size] * A[r_size] % MOD)
            B[j] += res % MOD
        A = B
    return A[n]


# n, m = map(int, input().split())
n, m = 3, 3
print(f(n, m))
print(g(n, m))
print(g2(n, m))
